// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 技巧：
// 使用滚动数组进行优化：删除横坐标，从右往左填表

// 例题 3:
// 给你一个非负整数数组 nums 和一个整数 target 。
//
//        向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
//
//        例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
//        返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
//
//        示例 1：
//
//        输入：nums = [1,1,1,1,1], target = 3
//        输出：5
//        解释：一共有 5 种方法让最终目标和为 3 。
//        -1 + 1 + 1 + 1 + 1 = 3
//        +1 - 1 + 1 + 1 + 1 = 3
//        +1 + 1 - 1 + 1 + 1 = 3
//        +1 + 1 + 1 - 1 + 1 = 3
//        +1 + 1 + 1 + 1 - 1 = 3
//        示例 2：
//
//        输入：nums = [1], target = 1
//        输出：1
//
//
//        提示：
//
//        1 <= nums.length <= 20
//        0 <= nums[i] <= 1000
//        0 <= sum(nums[i]) <= 1000
//        -1000 <= target <= 1000

// 解题思路:
// dp[i][j] 表示 [0, i] 区间内选择数字和为 j 的方法数
// t = (sum + target) / 2
// if(t < 0 || (sum + target) % 2 == 1) return 0
// if(j >= nums[i]) dp[i][j] = dp[i - 1][j - nums[i]]
// dp[i][j] += dp[i - 1][j]
// 初始化：注意到当 nums[i] == 0 时，dp[i][0] = dp[i - 1][0 - nums[0]]，因此无需初始化第 0 列，放在填表过程中填即可
// 返回 dp[n][t]

public class FindTargetSumWays {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int x : nums) sum += x;
        int t = (sum + target) / 2;
        if(t < 0 || (sum + target) % 2 == 1) return 0;
        int[][] dp = new int[n + 1][t + 1];

        dp[0][0] = 1;

        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= t; j++){
                dp[i][j] = dp[i - 1][j];
                if(j - nums[i - 1] >= 0){
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][t];
    }
}
